package leetcode.all;

public class Solution33 {
    //搜索旋转排序数组
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length-1, mid = 0;
        while (l<=r){
            mid = (l+r)>>1;
            if(nums[mid]==target) return mid;
            if(nums[mid]>nums[r]){ //mid在左支，[l,mid]有序
                if(target>=nums[l]&&target<=nums[mid]){ //target在有序区间[l,mid]内
                    r = mid-1;
                }else{ //target不在[l,mid]
                    l = mid+1;
                }
            }else { //mid在右支，[mid,r]有序
                if(target>=nums[mid]&&target<=nums[r]){ //target在有序区间[mid,r]内
                    l = mid+1;
                }else{ //target不在[mid,r]
                    r = mid-1;
                }
            }
        }
        return -1;
    }
}
